package JZ_Offer.algorithm.backtracking;

/**
 * 请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，
 * 每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。
 * 例如
 * a b c e
 * s f c s
 * a d e e
 * 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
 */
public class JZ12_矩阵中的路径 {
    static char[] matrix;
    static int rows, cols, matrixSize, strSize;

    /**
     * rows行 cols列
     */
    public static boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
        JZ12_矩阵中的路径.matrix = matrix;
        JZ12_矩阵中的路径.rows = rows;
        JZ12_矩阵中的路径.cols = cols;
        JZ12_矩阵中的路径.matrixSize = matrix.length;
        JZ12_矩阵中的路径.strSize = str.length;

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (dfs(r, c, 0, str)) return true;
            }
        }
        return false;
    }

    /**
     * 当前处理的问题是什么，并且下一次在规模减小的情况下处理相同的问题。
     */
    private static boolean dfs(int r, int c, int pos, char[] str) {
        // 检查行列值是否越界
        if (r < 0 || r >= rows || c < 0 || c >= cols) {
            return false;
        }

        // 计算下标
        int index = c + r * cols;

        char ch = matrix[index];
        // 判断是否访问过 和 是否和str[pos]匹配
        if (ch == '#' || ch != str[pos]) {
            return false;
        }

        // 没有待匹配字符了 匹配成功
        if (pos == strSize - 1) {
            return true;
        }

        // 当前字符成功匹配，标记一下，下次不能再次进入
        // # 占位 很巧妙的标注哪些数据处理过了
        matrix[index] = '#';

        // 上下左右 寻找下一个字符
        if (dfs(r, c + 1, pos + 1, str)) {
            return true;
        }
        if (dfs(r, c - 1, pos + 1, str)) {
            return true;
        }
        if (dfs(r + 1, c, pos + 1, str)) {
            return true;
        }
        if (dfs(r - 1, c, pos + 1, str)) {
            return true;
        }

        // 回溯 此次匹配失败
        matrix[index] = ch;
        return false;
    }

    public static void main(String[] args) {
        char[] matrix = {'a', 'b', 'c', 'e', 's', 'f', 'c', 's', 'a', 'd', 'e', 'e'};
        char[] str = {'b', 'c', 'c', 'e', 'd'};
        char[] str2 = {'a', 'b', 'c', 'b'};
        boolean hasPath = hasPath(matrix, 3, 4, str);
        System.out.println(hasPath);
    }

}
